import profile

import sys
sys.setrecursionlimit(10000000)
def BubbleSort(data):
    flag = 0
    for i in range(len(data) - 1):
        for j in range(len(data) - 1 - i):
            if data[j] > data[j + 1]:
                flag = 1
                data[j], data[j + 1] = data[j + 1], data[j]
        if flag == 0:
            break
    f1.write(str(data))

def InsertSort(data):
    length = len(data)
    for i in range(1, length):
        x = data[i]
        for j in range(i, -1, -1):
            # j为当前位置，试探j-1位置
            if x < data[j-1]:
                data[j] = data[j-1]
            else:
                # 位置确定为j
                break
        data[j] = x
    f2.write(str(data))


def SelectSort(data):
    n = len(data)
    for j in range(n - 1):
        min_index = j
        for i in range(j + 1, n):
            if data[min_index] > data[i]:
                min_index = i
        data[j], data[min_index] = data[min_index], data[j]
    f3.write(str(data))

def sort(data):
    sorted(array)
    f4.write(str(data))

def QuickSort(myList,start,end):
    if start < end:
        i, j = start, end
        base = myList[i]

        while i < j:
            while (i < j) and (myList[j] >= base):
                j = j - 1

            myList[i] = myList[j]

            while (i < j) and (myList[i] <= base):
                i = i + 1
            myList[j] = myList[i]
        myList[i] = base

        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


def merge_sort( li ):
    if len(li) == 1:
        return li

    mid = len(li) // 2
    left = li[:mid]
    right = li[mid:]

    ll = merge_sort( left )
    rl =merge_sort( right )

    return merge(ll , rl)

def merge( left , right ):
    result = []
    while len(left)>0 and len(right)>0 :
        if left[0] <= right[0]:
            result.append( left.pop(0) )
        else:
            result.append( right.pop(0) )
    result += left
    result += right
    return result


def profileTest():
    BubbleSort(array)
    InsertSort(array)
    SelectSort(array)
    sort(array)
    QUICKSORT = QuickSort(array, 0, len(array)-1)
    f6.write(str(QUICKSORT))
    MERGESORT = merge_sort(array)
    f5.write(str(MERGESORT))

fo = open("number.txt", "r")
f1 = open("BubbleSort.txt", "w+")
f2 = open("InsertSort.txt", "w+")
f3 = open("SelectSort.txt", "w+")
f4 = open("Sort.txt", "w+")
f5 = open("MergeSort.txt", "w+")
f6 = open("QuickSort.txt", "w+")

array = list(fo)
array = list(map(int, array))

if __name__ == "__main__":
    profile.run("profileTest()")


